#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define szARR(x) sizeof(x) / sizeof(x[0])
#define DBG_PRINTF
#define MAXN 10000 // Windows下溢出可能有不正确的结果,LINUX下溢出会RE。
int cvt[MAXN][2], f[MAXN], q[1000 * 1000], head, tail;

int SplitNum(int n, int *ptr)
{
   int cnt = 0;
   if (n == 0)
   {
      ptr[0] = 0;
      cnt = 1;
   }
   else
   {
      while (n)
      {
         ptr[cnt++] = n % 10;
         n /= 10;
      }
   }
   return cnt;
}

int CombNum(int len, int *ptr)
{
   int cnt = 0, n = 0, xx = 1;
   while (len--)
   {
      n += ptr[cnt++] * xx;
      xx *= 10;
   }

   return n;
}

int main()
{
   int n, k, ans = 1;
   cin >> n >> k;

   for (int i = 0; i < k; i++)
      cin >> cvt[i][0] >> cvt[i][1];
   int cnt = 0;
   q[tail++] = n;
   f[n] = 1;
   while (head != tail)
   {
      int num[100];
      int len = SplitNum(q[head++], num);
      for (int i = 0; i < len; i++)
      {
         for (int j = 0; j < k; j++)
         {
            if (cvt[j][0] == num[i])
            {
               int numNew[100];
               //memcpy(numNew, num, len); // xxxx . bug!
               memcpy(numNew, num, sizeof(numNew));
               numNew[i] = cvt[j][1];
               int newN = CombNum(len, numNew);
               if (!f[newN])
               {
                  f[newN] = 1;
                  q[tail++] = newN;
                  ans++;
               }
            }
         }
      }
   }
   cout << ans;
   return 0;
}
